package dem1;

import java.util.Stack;

/**
 * Created with Intellij IDEA.
 * Description:
 * User: 33013
 * Date: 2023-04-23
 * Time: 22:24
 */

class Solution {
    public int posindex = 0;

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        posindex = postorder.length - 1;
        return buildChildTree(inorder, postorder, 0, inorder.length - 1);
    }
    private TreeNode buildChildTree(int[] inorder, int[] postorder, int inbegin, int inend){
        if(inbegin > inend ){
            return null;
        }
        TreeNode root = new TreeNode(postorder[posindex]);
        int x = find(inorder, postorder[posindex], inbegin, inend);
        posindex--;
        root.left = buildChildTree(inorder, postorder, inbegin, x - 1);
        root.right = buildChildTree(inorder, postorder, x + 1, inend);
        return root;
    }

    private int find(int[] inorder, int x, int inbegin, int inend){
        for(int i = inbegin; i <= inend; i++){
            if(inorder[i] == x){
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] inorder = {9,3,15,20,7};
        int[] posorder = {9,15,7,20,3};
        Solution solution = new Solution();
        TreeNode tree = solution.buildTree(inorder,posorder);
    }
}


public class Test {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.pop();
        int[] arr;
        StringBuilder stringBuilder = new StringBuilder();
    }
}
